ABC057 C - Digits in Multiplication
Submission #13433003 - AtCoder Beginner Contest 057
解説PDF
AtCoder ABC 057 C - Digits in Multiplication (緑色, 300 点) - けんちょんの競プロ精進記録
$ N=A×B
を満たす
$ (A,B)
を全探索する
$ A=1,2,…,\sqrt{N}
まで考える
$ N \% A == 0
⇒
$ B=\frac{N}{A}
として、
$ (A,B)
が候補
$ A \le \sqrt{N}
で良い理由づけ
暗黙的に
$ A \le B
仮に、
$ A>\sqrt{N}
にすると、
$ A \times B > N
となり矛盾する
探索数を減らす全探索